package 链表;

/**
 * 61:旋转链表
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 * 思路：k个位置有可能大于链表的长度，那么减去周期长度也就是取余即可。
 *
 * 解题步骤：
 *  1.计算链表的长度n；
 *  2 处理k的值：如果 k 大于链表的长度 n，那么旋转 k 次相当于旋转 k % n 次（因为旋转 n 次链表会回到原样）。
 *  3：找到旋转点，找到链表的倒数第 k 个节点，这个节点将是新链表的尾节点，其下一个节点将是新链表的头节点。
 *  4：断开链表：将链表断开，形成两个子链
 *  5：将第二个子链的尾结点连接到第一个子链的头结点，形成旋转后的链表
 */
public class L_61 {

    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null || k == 0){
            return head;
        }
        // 计算链的长度
        int n =1;
        ListNode tail = head;
        while (tail.next != null){
            tail = tail.next;
            n++;
        }
        // 处理k的值
        k = k % n;
        if(k == 0){ // 如果刚好是链表长度的整数倍，直接返回原链表
            return head;
        }
        // 找到旋转节点 （要断开节点的前驱节点，k-n-1）
        ListNode newTail = head;
        for (int i = 0; i < n - k - 1; i++) {
            newTail = newTail.next;
        }

        // 断开链表重新连接
        ListNode newHead = newTail.next;
        newTail.next = null;
        // tail本来就是原链表的尾部，直接指向原链表的头结点
        tail.next = head;

        return newHead;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

    }

}